int m;
int n;
bool used[21][21] = { false };
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

bool dfs(vector<vector<char> >& matrix, int x, int y, int pos, string& word)
{
    if (pos == word.size())
    {
        return true;
    }
    for (int k = 0; k < 4; k++)
    {
        int newx = x + dx[k];
        int newy = y + dy[k];
        if (newx >= 0 && newx < m && newy >= 0 && newy < n && !used[newx][newy] && matrix[newx][newy] == word[pos])
        {
            used[newx][newy] = true;
            if (dfs(matrix, newx, newy, pos + 1, word))return true;
            used[newx][newy] = false;

        }





    }
    return false;







}
bool hasPath(vector<vector<char> >& matrix, string word) {
    m = matrix.size();
    n = matrix[0].size();
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (matrix[i][j] == word[0])
            {
                used[i][j] = true;
                if (dfs(matrix, i, j, 1, word))return true;
                used[i][j] = false;
            }




        }
    } return false;
}
};
class Solution {
public:
    int m;
    int n;
    int count = 0;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    bool used[101][101];
    bool isgo(int x, int y, int threshold)
    {
        int num = 0;
        while (x)
        {
            num += x % 10;
            x /= 10;



        }
        while (y)
        {
            num += y % 10;
            y /= 10;
        }
        return num <= threshold;




    }
    void dfs(int x, int y, int threshold)
    {
        count++;
        for (int k = 0; k < 4; k++)
        {
            int newx = x + dx[k];
            int newy = y + dy[k];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && !used[newx][newy] && isgo(newx, newy, threshold))
            {
                used[newx][newy] = true;
                dfs(newx, newy, threshold);


            }




        }








    }
    int movingCount(int threshold, int rows, int cols) {
        m = rows;
        n = cols;
        used[0][0] = true;
        dfs(0, 0, threshold);
        return count;






    }
};
class Solution {
public:
    int m;
    int n;
    bool used[301][301];
    int count = 0;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    void dfs(vector<vector<char>>& grid, int x, int y)
    {
        used[x][y] = true;
        for (int k = 0; k < 4; k++)
        {
            int newx = x + dx[k];
            int newy = y + dy[k];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && !used[newx][newy] && grid[newx][newy] == '1')
            {
                dfs(grid, newx, newy);


            }




        }






    }




    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && !used[i][j])
                {
                    count++;
                    dfs(grid, i, j);



                }




            }
        }




        return count;

    }

}; class Solution {
public:
    int m;
    int n;
    int result = 0;
    bool used[16][16];
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    void dfs(vector<vector<int>>& grid, int x, int y, int path)
    {
        result = max(result, path);
        for (int k = 0; k < 4; k++)
        {
            int newx = x + dx[k];
            int newy = y + dy[k];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && !used[newx][newy] && grid[newx][newy])
            {
                used[newx][newy] = true;
                dfs(grid, newx, newy, path + grid[newx][newy]);
                used[newx][newy] = false;





            }




        }








    }

    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j])
                {
                    used[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    used[i][j] = false;


                }






            }
        }



        return result;






    }
};
class Solution {
public:
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    bool used[51][51];
    int res;
    int m;
    int n;
    void dfs(vector<vector<int>>& image, int x, int y, int color)
    {
        image[x][y] = color;
        for (int k = 0; k < 4; k++)
        {
            int newx = x + dx[k];
            int newy = y + dy[k];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && !used[newx][newy] && image[newx][newy] == res)
            {
                used[newx][newy] = true;
                dfs(image, newx, newy, color);



            }






        }






    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        m = image.size();
        n = image[0].size();
        res = image[sr][sc];
        if (res == color)
            return image;
        dfs(image, sr, sc, color);
        return image;
    }
};
class Solution {
public:
    int m;
    int n;
    bool used[51][51];
    int count = 0;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
    int result = 0;
    void dfs(vector<vector<int>>& grid, int x, int y, int* pi)
    {
        (*pi)++;
        used[x][y] = true;
        for (int k = 0; k < 4; k++)
        {
            int newx = x + dx[k];
            int newy = y + dy[k];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && !used[newx][newy] && grid[newx][newy])
            {
                dfs(grid, newx, newy, pi);
            }





        }







    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && !used[i][j])
                {
                    int count = 0;
                    dfs(grid, i, j, &count);
                    result = max(result, count);

                }



            }
        }
        return result;







    }
};